#include "game.h"
#include<bits/stdc++.h>

namespace yyyyxh{
	using namespace std;
	#define rg register
	random_device rd;
	mt19937_64 rnd(rd());
	int n,Get;
	const int maxn=5e3+10;
	int Ans[maxn];
	bool vis[maxn];
	vector<int>_P;
	int ____;
	inline bool test(int l,int r)
	{
		int Low=0;
		for(rg int i=l;i<=r;i+=1)Low+=_P[i-1]==Ans[i];
		vector<int>Out;
		for(rg int i=1;i<l;i+=1)Out.emplace_back(_P[i-1]);
		for(rg int i=r+1;i<=n;i+=1)Out.emplace_back(_P[i-1]);
		for(rg int Case=1;Case<=5;Case+=1)
		{
			vector<int>S2;
			shuffle(Out.begin(),Out.end(),rnd);
			auto S1=Out;
			for(rg int i=1;i<l;i+=1)S2.emplace_back(S1.back()),S1.pop_back();
			for(rg int i=l;i<=r;i+=1)S2.emplace_back(_P[i-1]);
			for(rg int i=r+1;i<=n;i+=1)S2.emplace_back(S1.back()),S1.pop_back();
			if(count(S2)==Low)return false;
		}
		return true;
	}
	inline void solve(int l,int r)
	{
		if(____==Get)return;
		if(l==r)
		{
/*			if(l==4)
			{
				cerr<<"???"<<test(4,4)<<endl;;exit(0);
				}*/
			if(Ans[l])return;
			Ans[l]=_P[l-1];
			vis[Ans[l]]=true;
			++Get;return;
		}
		int mid=(l+r)>>1;
		if(____>Get&&test(l,mid))solve(l,mid);
		if(____>Get&&test(mid+1,r))solve(mid+1,r);
	}
	inline void solve(vector<int>P)
	{
		_P=P;
		solve(1,n);
	}
	inline vector<int>main(int _n,int limit)
	{
		n=_n;
		for(rg int i=1;i<=n;i+=1)Ans[i]=0,vis[i]=false;Get=0;
//		for(rg int Case=1;Case<=10&&Get<n;Case+=1)
		set<vector<int> >S;
		while(Get<n-5)
		{
//			cerr<<Get<<endl;
//			for(rg int i=1;i<=n;i+=1)cerr<<Ans[i]<<" ";cerr<<endl;
//			for(rg int i=1;i<=n;i+=1)cerr<<vis[i]<<" ";cerr<<endl;
			vector<int>P;
			for(rg int i=1;i<=n;i+=1)if(!vis[i])P.emplace_back(i);
			shuffle(P.begin(),P.end(),rnd);
			vector<int>Send;
			for(rg int i=1;i<=n;i+=1)
				if(Ans[i])Send.emplace_back(Ans[i]);
				else Send.emplace_back(P.back()),P.pop_back();
			if(S.count(Send))continue;
			S.emplace(Send);
			____=count(Send);
			if(____==n)return Send;
			if(____>Get)
			{
//				for(auto x:Send)cerr<<x<<" ";cerr<<endl;
//				cerr<<____<<"!!!"<<endl;
//				cerr<<count(Send)<<"!!!"<<endl;
				solve(Send);
			}
		}
		vector<int>Rest;
		for(rg int i=1;i<=n;i+=1)if(!vis[i])Rest.emplace_back(i);
		do{
			auto S1=Rest;
			vector<int>Send;
			for(rg int i=1;i<=n;i+=1)
				if(Ans[i])Send.emplace_back(Ans[i]);
				else Send.emplace_back(S1.back()),S1.pop_back();
			if(count(Send)==n)
			{
				for(rg int i=1;i<=n;i+=1)Ans[i]=Send[i-1];
				break;
			}
		}while(next_permutation(Rest.begin(),Rest.end()));
		vector<int>re;
		for(rg int i=1;i<=n;i+=1)re.emplace_back(Ans[i]);
		return re;
	}
}

std :: vector<int> guess(int n, int limit) {
	return yyyyxh::main(n,limit);
	std :: vector<int> ans;
	ans.resize(n);
	for(int i = 1; i <= n; i ++)
		ans[i - 1] = i;
	return ans;
}
